package com.atwy.recursion;

/**
 * 递归 ：方法自己调用自己。
 * 能解决什么问题：
 * 1、8皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子问题
 * 2、快排，归并排序，二分查找，分治算法等
 * <p>
 * 迷宫问题：
 *  初始位置在(1,1),迷宫出口在(6,5)
 *  使用递归回溯找到出口
 *  说明：
 *      1、map表示地图
 *      2、i,j表示从地图的哪个位置开始触发(1,1)
 *      3、如果能到map[6][5]位置，说明通路找到
 *      4、约定：当map[i][j]为 0 表示该点没有走过，当为 1 表示墙；
 *          为 2 表示通路可以走，3 表示该点已经走过，但走不通
 *      5、在走迷宫时，需要确定一个策略（方法）下 -> 右 -> 上 -> 左，如果该点走不通，再回溯
 *
 *      路径与找路策略有关
 *
 */
public class MiGong {

    public static void main(String[] args) {
        // 先创建一个二维数组，模拟迷宫
        // 地图
        int[][] map = new int[8][7];
        // 使用 1 表示墙
        // 上下全部置为 1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        // 左右全部置为 1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //设置挡板, 1 表示
        map[3][1] = 1;
        map[3][2] = 1;
        // map[1][2] = 1;
        // map[2][2] = 1;
        // 输出地图
        System.out.println("地图的情况");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        // 策略：下 -> 右 -> 上 -> 左
        //setWay(map,1,1);
        setWay2(map,1,1);
        System.out.println("小球走过，并标识过的 地图的情况");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }



    }

    /**
     *      1、map表示地图
     *      2、i,j表示从地图的哪个位置开始触发(1,1)
     *      3、如果能到map[6][5]位置，说明通路找到
     *      4、约定：当map[i][j]为 0 表示该点没有走过，当为 1 表示墙；
     *          为 2 表示通路可以走，3 表示该点已经走过，但走不通
     *      5、在走迷宫时，需要确定一个策略（方法）下 -> 右 -> 上 -> 左，如果该点走不通，再回溯
     * @param map 地图
     * @param i 行
     * @param j 列
     * @return true:找到通路
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if(map[6][5] == 2){
            // 通路已找到
            return true;
        }else{
            if(map[i][j] == 0){// 这个点没走过
                // 下 -> 右 -> 上 -> 左
                // 假设该点可以走通
                map[i][j] = 2;
                if(setWay(map,i+1,j)){
                    return true;
                }else if(setWay(map,i,j+1)){
                    return true;
                }else if(setWay(map,i-1,j)){
                    return true;
                }else if(setWay(map,i,j-1)){
                    return true;
                }else{
                    // 走不通
                    map[i][j] = 3;
                    return false;
                }

            }else{// 该点走过，很明显没找到
                return false;
            }
        }

    }

    /**
     * 策略2： 上->右->下->左
     * @param map
     * @param i
     * @param j
     * @return
     */
    public static boolean setWay2(int[][] map, int i, int j) {
        if(map[6][5] == 2){
            // 通路已找到
            return true;
        }else{
            if(map[i][j] == 0){// 这个点没走过
                // 上->右->下->左
                // 假设该点可以走通
                map[i][j] = 2;
                if(setWay(map,i-1,j)){
                    return true;
                }else if(setWay(map,i,j+1)){
                    return true;
                }else if(setWay(map,i+1,j)){
                    return true;
                }else if(setWay(map,i,j-1)){
                    return true;
                }else{
                    // 走不通
                    map[i][j] = 3;
                    return false;
                }

            }else{// 该点走过，很明显没找到
                return false;
            }
        }

    }
}
